#include<iostream>
#include<vector>
using namespace std;
bool duplicate(vector<int>& nums,int* ans) {
	if (nums.size() == 0) { return false; }
	int n = nums.size();
	for (int i = 0; i < n; ++i) {
		if (nums[i] < 0 || nums[i] >= n) { return false; }
	}
	for (int i = 0; i < n; ++i) {
		while (nums[i] != i) {
			if (nums[i] == nums[nums[i]]) {
				*ans = nums[i];
				return true;
			}
			swap(nums[i], nums[nums[i]]);
		}
	}
	return false;
}
bool contain(vector<int>& expect, int number) {
	for (int num : expect) {
		if (num == number) {
			return true;
		}
	}
	return false;
}
void test(char* testName,vector<int>& nums,vector<int>& expect,bool validArgument) {
	cout << testName <<" begins:"<<endl;
	int duplication;
	bool validInput = duplicate(nums, &duplication);
	if (validInput == validArgument) {
		if (!validInput) {
			cout << "passed" << endl;
		}
		else if (contain(expect, duplication)) {
			cout << "passed" << endl;
		}
		else {
			cout << "failed" << endl;
		}
	}
	else {
		cout << "faild" << endl;
	}
}

void test1() {
	vector<int> nums = { 2,1,3,1,4 };
	vector<int> expect = { 1 };
	test((char*)"test1", nums, expect, true);
}
void test2() {
	vector<int> nums = { 2,4,3,1,4 };
	vector<int> expect = { 4 };
	test((char*)"test2", nums, expect, true);
}
void test3() {
	vector<int> nums = { 2,4,2,1,4 };
	vector<int> expect = { 4,2 };
	test((char*)"test3", nums, expect, true);
}
void test4() {
	vector<int> nums = { 2,1,3,0,4 };
	vector<int> expect = { -1 };
	test((char*)"test4", nums, expect, false);
}
void test5() {
	vector<int> nums = { 2,1,3,5,4 };
	vector<int> expect = { -1 };
	test((char*)"test5", nums, expect, false);
}
void test6() {
	vector<int> nums;
	vector<int> expect = { -1 };
	test((char*)"test6", nums, expect, false);
}
int main(int argc,char* argv[]) {
	test1();
	test2();
	test3();
	test4();
	test5();
	test6();
	return 0;
}